The present invention relates to data communication systems for transferring information in packets and more particularly, to scheduling packets in a wireless communications network using polling.
In many conventional packet-oriented data communications networks, the data traffic between units may be controlled by one centralized unit. In such networks, the central unit may be referred to as a server and the remaining units are denoted as clients. All data packets destined for a particular unit or xe2x80x9cnodexe2x80x9d in the network pass through the central node. Moreover, a client node may not generally send data without first being polled by the server unit.
In client-server oriented network architectures, communications channels between a server unit and client units are generally bidirectional and may use either wireline or wireless transmission technology. In the case of a shared channel in either a wireline or wireless network, total data transfer capacity may be shared among one or more clients. A server unit in such a network is therefore responsible for distributing channel capacity among the various clients according to some predefined rule or algorithm. Common methods for distributing channel capacity may include known polling algorithms.
According to typical polling algorithms, the server may address each client in a predetermined sequence. When a client is polled by a server, the polled client has an opportunity to transfer any data which may be queued. If no data is queued, then the server simply moves to the next client in sequence to see if the next client has data for transfer and so on.
One example of a wireless communication system which uses polling to facilitate channel sharing is described in the publication entitled xe2x80x9cSpecification of the Bluetooth Systemxe2x80x9d, published by the Bluetooth SIG, v1.0, Jul. 26 ,1999. The Bluetooth (BT) system is an exemplary technology for ad-hoc networking developed for short range wireless connectivity. Bluetooth is based on a short-range, universal radio link, and it provides a mechanism to form small ad-hoc groupings of connected devices, without a fixed network infrastructure, including such devices as printers, PDAs, desktop computers, FAX machines, keyboards, joysticks, telephones, or virtually any device capable of digital communication.
To better appreciate the operation of a Bluetoothstyle system, the following definitions may be useful.
Piconet: a sub-network that is part of a larger Bluetooth (BT) network, a piconet generally includes one master node and one or more slave nodes. The description of the centrally controlled network in the previous section may be applied generally to a Bluetooth piconet with a series of piconets making up a Bluetooth network.
Bluetooth node: a network node in a piconet which may take on the role of either master or slave. A Bluetooth node may also act as a master and simultaneously as a slave in more than one piconet, however, may be master in only one piconet.
Master: a Bluetooth node which may control all traffic in a piconet and which may act as a server node in accordance with the description of the centrally controlled network given above.
Slave: a Bluetooth node which may be controlled by one master and which may act as a client node in the introductory description above. A piconet may host several slaves simultaneously.
As previously described, Bluetooth systems allow for wireless connectivity between, for example, mobile PCs, phones, digital cameras, proximity detectors, and other portable devices. Bluetooth systems may operate on the unlicensed 2.4 Ghz band which poses some risk of connections collision with 802.11 wireless LANs. Bluetooth systems are nevertheless desirable however due to their low power requirements coupled with the shortness of their range, e.g. up to 10 meters making them useful for interoffice wireless applications. While 802.11 wireless LANs operate with ranges up to several hundred feet. It may be important therefore for Bluetooth systems to be tolerant of possible interference from 802.11 wireless LANs.
A wireless channel in a typical Bluetooth system may use time division duplex (TDD) to achieve a bidirectional link between a master and a slave. When data is transferred on the Bluetooth TDD channel, one packet may first be sent from a master to a slave directly followed by a packet sent from a slave to a master. Moreover, the Bluetooth packet size used in either of the directions may occupy, for example, 1, 3, or 5 slots, where one slot is 0.625 ms wide. The Bluetooth specification, supra, may also support circuit switched traffic on a dedicated logical link denoted synchronous connection oriented (SCO) link, as may typically be used for voice applications. Packets associated with an SCO link may be carried periodically, for example, in every slot, in every second slot, or in every third slot. In contrast, traffic on a dedicated logical link not necessarily associated with circuit switching and more oriented toward data transfer as opposed to voice transfer may be denoted as an asynchronous connectionless link (ACL),
In order to control bandwidth utilization and achieve high levels thereof, within, for example, a Bluetooth piconet, a master may control data flow on a communication channel by polling slaves for every data packet sent on the channel in an up-link (UL) direction from the controlled unit to the controlling unit, e.g., slave to master. However, traffic on SCO links is generally sent on an UL without polling in contrast to ACL links where polling is a necessity. A poll from a master node may be in the form of a data packet, thus creating the possibility of a bidirectional data flow on an SCO link at the polling instant if UL traffic is present. In the downlink (DL) direction from the controlling unit to the controlled unit, e.g., master to slave, no polling is generally required to send a packet since slaves are expected to be normally idle unless being polled.
In addition to controlling data flow to and from slaves in most circumstances using polling as described, a master may control packet size used by a slave to achieve precise control of bandwidth and delay in the piconet. Accordingly, control over, for example Quality of Service (QoS) levels, particularly as they relate to delay factors may be achieved. It may be assumed, however, for simplicity in the foregoing and following description unless otherwise noted, that a typical piconet supports best effort (BE) traffic only. Fair distribution of the available resources may nevertheless be applied to the use of polling algorithms even in support of BE traffic.
The particular manner in which a master may poll one or more slaves, is important to ensure proper bandwidth utilization in a piconet. Generally, data traffic within a piconet may exhibit bursty characteristics stemming from, for example, user behavior, application, and protocol mechanisms, e.g., TCP flow control, retransmissions, and the like. For such bursty data traffic, and given that assumption, as described that a Bluetooth piconet supports BE packets, fair distribution of channel resources becomes an important consideration. I may further be important that master-slave pairs having traffic to send be given as much capacity as possible, while maintaining fairness in distribution of channel resources.
Polling algorithms are fairly well known and documented, and several examples may be found in the literature, see, for example, xe2x80x9cQueuing Analysis of Polling Modelsxe2x80x9d, Hideaki Takagi, ACM Computing Surveys, Vol. 20, No. 1, March 1988. For a better understanding of however, particularly in the context of Bluetooth piconets, short descriptions of three generic polling algorithms are provided herein below.
A first polling algorithm known in the art is the Round Robin (RR) polling algorithm. RR polling represents a simple way of polling slaves in a piconet. In accordance with RR polling, slave nodes may be polled in sequence according to a circular list. During each polling contact by a master node, each slave node may be allowed to send one or more packets the size of which may be fixed at 1,3, or 5 time slots as previously described. Likewise, a master node may send one or more DL packets to a slave node only during a polling contact preferably in a one-for-one exchange as may be associated with, for example, a TDD channel as previously described. Assuming packets having single slot durations, the bandwidth share per master-slave pair, CMSpair in a pico-net with N nodes including a master node and no SCO traffic may be expressed by Equation (1) as follows:                                           C            MSpair                    =                      C                          N              -              1                                      ,                            (        1        )            
where C is the total link capacity in the piconet. If packets occupy more than one time slot, CMSpair could be greater than that given in Equation (1) where CMSpair may now be expressed by Equation (2).                               C          MSpair                =                              5            ⁢            C                                5            +            N            -            2                                              (        2        )            
Equation (2) may be applied to a case where one master-slave pair is active and packets occupying, for example, as many as 5 time slots are used. Simulations have shown that the use of multislot packets may significantly improve the handling of bursty traffic, as may be described in, for example, xe2x80x9cShort Range Radio Based Ad-hoc Networking: Performance and Propertiesxe2x80x9d, P. Johansson, N. Johansson, U. Kxc3x6rner, J. Elg, G. Svennarp, Proceedings of International Conference on Communications (ICC""99), Jun. 6-10 1999.
A second known polling algorithm may be referred to as Exhaustive Polling (EP). EP allows channel capacity to be dynamically focused to a master-slave pair most in need of greater capacity. EP algorithms conduct a poll of all active slave nodes in a circular fashion similar to RR polling. However, when a slave node having data to transfer, e.g. a non-empty UL queue, is polled by a master, the EP algorithm allows the slave to continue transferring data until the UL queue has been emptied. If new packets are queued prior to emptying a queue, the new packets are also transferred. It is important to note that when conducting EP, for example, in a Bluetooth piconet, the sum of the UL and DL queue contents for a particular master-slave pair should be taken into consideration since the channel is bidirectional. Otherwise, a master node may be polled separately to complete the EP cycle. It should further be noted, however, that EP schemes have inherent fairness problems since a slave having dominant flow of data to transfer may seize the shared channel for a long period of time; since new packets may arrive continuously, the time period may be indefinite.
If no admission control is performed on a per piconet basis, for example, by placing a limit on total traffic load between any particular master-slave pair, traffic streams associated with other master-slave pairs may get starved for indefinite time periods. If admission control is performed, the use of EP schemes may still result in very high delay variations, but will still provide high channel utilization. It should be noted that in order to achieve high throughput, packets should be as long as possible once data is sent to/from a slave. By increasing packet length, overhead per packet may be reduced thus increasing throughput for each master slave pair. Tradeoffs between packet size and packet overhead along with other link requirements may need to be considered to find optimal utilization and throughput. For example, packets occupying up to five time slots may provide good utilization, provided that, for example, SCO links are not present.
A third known polling algorithm may be referred to as Gated Polling (GP). To counter starvation problems associated with EP schemes, Gated Polling (GP) may be used. Polling characteristics similar to EP may be applied generally in GP, however a slave""s UL queue may be emptied up to the number of packets that were present when the polling interval began. Thus, new packets queued after polling begins are not transferred until the next polling interval. Subsequent nodes are polled in a similar manner according to a predetermined sequence, e.g. circular.
GP may prevent nodes starvation during bursty traffic conditions, however fairness must be considered on a per burst level, e.g. a node with long bursts queued upon polling will transfer more data than nodes with smaller queue levels. Moreover, overall delay variation may be higher than for EP since data transfer flow is disrupted and delayed until the next polling interval. Since the beginning of the next interval is dependent on queue levels associated with other slave nodes it will occur at a random time.
It should be noted that channel utilization may be lower in GP than in EP schemes since polling after a xe2x80x9cgatedxe2x80x9d flow may result in a sequence of polls of empty queues, or empty poll packets, until the previously gated flow is resumed again during the next poll interval of that queue. As with EP, packets should be as long as possible, e.g. occupy as many time slots as possibly, once data is sent from a queue.
Although some shortcomings of the above described and well known polling schemes have been indicated in terms of delivering efficient and fair service to various slave nodes in a network, several additional problems arise when contemplating which polling algorithm is best suited for use in a Bluetooth system.
A first problem may arise in that it may be possible for some slave units to have delay tolerance requirements which affect the maximum time between two successive poll intervals. Accordingly, any polling algorithm used must ensure that nodes having such delay tolerance requirements are serviced by a master unit within the required time limits.
A second problem may arise in that additional traffic types other than BE traffic may generally be controlled by the master unit. For example, data packets carrying information for circuit emulation services or network management may be handled by a master unit. Accordingly, any polling algorithm used in such a situation must allow transmission of a diversity of packets types in accordance with the requirements unique to each particular service which means that assumptions related to BE transmission may not be valid when different data types are being handled.
A third problem may arise in that a delay may exist between a point in time when a master unit decides to poll a particular slave unit and the point in time when the poll is actually conducted. Usually, this delay is seen as the delay between when a polling instant actually begins at the master and when a polling packet is sent to, or received at the slave unit. Such a delay may be the result of batched information exchange, e.g. pre-scheduling a certain number of packets before actually being queued at the master unit""s transceiver. Such a delay gives rise to cumulative delay in that an ultimate reaction by a master unit based on a delayed response from a slave unit will also be delayed. For any polling algorithm used in such a situation polling delay could mean that a master must handle the corresponding delays in any feedback information originating from the slave units.
It would therefore be desirable to provide a polling method for conducting polling in, for example, a Bluetooth or similar ad-hoc wireless system, which fairly distributed channel access between a master and one or more slave units, and which provides improved channel utilization.
It is therefore an object of the present invention to provide a method for improving the performance of polling based packet switching communication systems such as Bluetooth piconet systems.
It is a further object of the present invention to improve delay factors by taking into account batched information exchange between a master and one or more slaves.
Therefore, in accordance with one aspect of the present invention, the foregoing and other objects are achieved in a method for improving channel utilization and throughput in an ad-hoc wireless communication system having a master unit and one or more slave units, the master unit configured to control the one or more slave units, coupled with a shared communication channel having at least an uplink (UL) channel and a downlink channel (DL) for each master unit-slave unit pair. The method may have steps including establishing a group of active nodes corresponding to one or more of the one or more slave units having UL and/or DL data associated therewith for transfer; polling the group of active nodes according to Fair Exhaustive Polling (FEP); alternately transferring information between the master and a next slave unit as polled according to FEP. It should be noted that alternately transferring may be as a result of a Time Division Duplex link established therebetween.
In accordance with another embodiment of the invention, information may be accumulated to be transferred to the next slave unit and one or more subsequently polled slave units in a batch, and respective portions the batch of information may alternately be transferred between the next slave unit and the one or more subsequently polled slave units during a polling interval associated with each of the next slave unit and the one or more subsequently polled slave units. Feedback information may be collected regarding the slaves and used to adjust polling.
In accordance with still another embodiment of the invention one or more links associated with the one or more slave units may be identified as lossy links due to, for example, increased Bit Error Rate (BER) and accompanying information loss resulting in a lower throughput. Accordingly, one or more virtual active nodes may be added to the group of active nodes, wherein one or more of the one or more virtual active nodes is associated with the each of the identified one or more lossy links. Virtual active nodes may allow additional polling time to be allocated to lossy links. Such determination may be made by evaluating a transmission parameter against a predetermined threshold for each of the one or more links and wherein if the threshold is exceeded the link is identified as lossy, and wherein if the threshold is not exceeded the link is not identified as lossy. The predetermined threshold may include for example, a retransmission parameter. When the one or more links associated with the one or more slave units are no longer lossy the one or more virtual active nodes corresponding thereto may be removed from the group of active nodes.
In accordance with yet another embodiment of the present invention, information transferred between the master and one or more slaves may be associated with one or more of circuit switched synchronous information and non-circuit switched asynchronous information. It may further be possible to evaluating feedback information associated with the one or more slave units to determine for example whether the UL queue is empty or the like and thus polling may be suspended for such a slave unit. Further, during polling, a time out signal may be received associated with one or more of the one or more slave units. Accordingly the corresponding timed out slave units may be scheduled for polling responsive to the time out signal.